9627. a^b^c
Find the
value of
(mod 109 + 7)
Input.
The
first
line contains the number of test cases n.
Each of the next n lines contains
three numbers a, b, c (a, b, c ≤ 109).
Output. For each test
case print in a separate line the value of (mod 109 + 7).
|
Sample
input |
Sampple
output |
|
3 3 7 1 15 2 2 3 4 5 |
2187 50625 763327764 |
SOLUTION
exponentiation
Algorithm analysis
By Fermat's
little theorem ap – 1 = 1 (mod p), where p is prime. The number p = 109 + 7 is prime. Hence, for example,
it follows that a(p – 1) * l = 1 (mod p) for any number l.
To evaluate the expression a^b^c first
find k = bc, then calculate ak. However, the number bc is large, we
represent it in the form bc = (p – 1) * l + s for some l and s < p – 1. Then
a^(b^c) mod
p = a(p – 1) * l + s mod p = (a(p – 1) * l * as) mod p = as mod p
It’s obvious that s = bc mod (p – 1). Hence
a^(b^c) mod
p = a^(b^c mod (p – 1)) mod p
Example
Let’s calculate the value
of 3^2^3 mod 7. Module 7 is chosen to be prime. The value of expression is
3^(2^3) mod 7 = 38 mod 7 = 6561 mod 7 = (937 * 7 + 2)
mod 7 = 2
Fermat's theorem
implies that 36 mod 7 = 1. Therefore,
for any positive
integer k
(36 mod 7)k = 36k mod 7 = 1
Since 2^3 = 23 = 8, then 38 mod 7 = 36 * 1 + 2 mod 7 = 32 mod 7 = 9 mod 7 = 2
The original
expression can also be evaluated as
3^(2^3) mod 7 = 38 mod 7 = 38 mod 6 mod 7 = 32 mod
7 =
9 mod 7 = 2
Algorithm realization
Function powmod finds the value of xn mod m.
long long powmod(long long x, long long n, long long m)
{
if (n == 0) return 1;
if (n % 2 == 0) return
powmod((x * x) % m, n / 2, m);
return (x *
powmod(x, n - 1, m)) % m;
}
The main
part of the program. Read the input data.
scanf("%d", &n);
while (n--)
{
scanf("%lld
%lld %lld", &a, &b, &c);
Find the value
of res = bc
mod (p – 1).
res = powmod(b, c,
1000000006LL);
Find the value
of res = ares
mod p.
res = powmod(a, res,
1000000007LL);
Print the answer.
printf("%lld\n",
res);
}